//给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 
//
// 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。 
//
// 假设每一种面额的硬币有无限个。 
//
// 题目数据保证结果符合 32 位带符号整数。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：amount = 5, coins = [1, 2, 5]
//输出：4
//解释：有四种方式可以凑成总金额：
//5=5
//5=2+2+1
//5=2+1+1+1
//5=1+1+1+1+1
// 
//
// 示例 2： 
//
// 
//输入：amount = 3, coins = [2]
//输出：0
//解释：只用面额 2 的硬币不能凑成总金额 3 。
// 
//
// 示例 3： 
//
// 
//输入：amount = 10, coins = [10] 
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= coins.length <= 300 
// 1 <= coins[i] <= 5000 
// coins 中的所有值 互不相同 
// 0 <= amount <= 5000 
// 
// Related Topics 数组 动态规划 
// 👍 670 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class CoinChange2 {
    public static void main(String[] args) {
        Solution solution = new CoinChange2().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 完全背包的问题
     * dp[i][j]表示用前i个硬币得到j的组合数
     * 如何初始化是一个问题
     * 每一个硬币可以无限次取，那么dp[i][j] 与上一层的关系就是当前硬币取0-k次的累加
     * 即当j-k*coins[i]>=0的时候，遍历所有当前硬币
     * dp[i][j] = dp[i-1][j-0*c[i]] +dp[i-1][j-1*c[i]] + dp[i-1][j-2*c[i]] + dp[i-1][j-k*coins[i]]
     * 难点在于如何初始化以及如何压缩空间
     */
    class Solution {
        public int change(int amount, int[] coins) {
            int len = coins.length;
            if (len == 1) return amount % coins[0]==0 ? 1:0;///单个硬币判断
            int[][] dp = new int[len][amount+1];//初始化都是0
            dp[0][0] = 1 ; //这里是保证当前硬币恰好满足amount的情况
            for (int i = coins[0]; i <= amount ; i+=coins[0]) {
                dp[0][i] = 1;//初始化第一行，只有当前硬币的整数倍才可能取到
            }
            for (int i = 1; i < len ; i++) {
                for (int j = 0; j <=amount ; j++) {
                    for (int k = 0; j-k*coins[i]>=0 ; k++) {//遍历当前硬币能取到的所有情况
                        dp[i][j] += dp[i-1][j-k*coins[i]];
                    }
                }
            }
            return dp[len-1][amount];
        }

        /**
         * 优化状态转移方程，根据递推关系推导当前值和上一层值的关系
         * dp[i][j] = dp[i-1][j-0*c[i]]+
         *            dp[i-1][j-1*c[i]]+...+
         *            dp[i-1][j-k*c[i]]             （1）
         * 将j = j-c[i]代入上边，注意[]中必须>=0，得到
         * dp[i][j-c[i]] = dp[i-1][j-c[i]-0*c[i]]+
         *            dp[i-1][j-c[i]-1*c[i]]+...+
         *            dp[i-1][j-c[i]-(k-1)*c[i]]    （2）    这里是k-1，因为和（1）条件相同时最多取到k-1
         * 整理（2）得到如下结果
         * dp[i][j-c[i]] = dp[i-1][j-1*c[i]]+
         *            dp[i-1][j-2*c[i]]+...+
         *            dp[i-1][j-k*c[i]]            （3）
         * 将（1）和（3）做差可以得到
         * dp[i][j] - dp[i][j-c[i]] = dp[i-1][j]
         * 即为 dp[i][j] = dp[i-1][j] + dp[i][j-c[i]]
         *
         *
         * dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]]  当j>=coins[i]时成立
         * 所以当前值只要看左边的值，左边的值不存在至少是上一行的值，存在就加上左边的值
         */
        public int change2(int amount, int[] coins) {
            int len = coins.length;
            if (len == 1) return amount % coins[0]==0 ? 1:0;///单个硬币判断
            int[][] dp = new int[len][amount+1];//初始化都是0
            dp[0][0] = 1 ; //这里是保证当前硬币恰好满足amount的情况
            for (int i = coins[0]; i <= amount ; i+=coins[0]) {
                dp[0][i] = 1;//初始化第一行，只有当前硬币的整数倍才可能取到
            }
            for (int i = 1; i < len ; i++) {
                for (int j = 0; j <=amount ; j++) {
                    dp[i][j] = dp[i-1][j];
                    if (j-coins[i]>=0) dp[i][j]+= dp[i-1][j-coins[i]];
                }
            }
            return dp[len-1][amount];
        }


        /**
         * 压缩空间到一维
         */
        public int change3(int amount, int[] coins) {
            int len = coins.length;
            if (len == 1) return amount % coins[0]==0 ? 1:0;///单个硬币判断
            int[] dp = new int[amount+1];//初始化都是0
            dp[0] = 1 ; //这里是保证当前硬币恰好满足amount的情况
            for (int i = coins[0]; i <= amount ; i+=coins[0])
                dp[i] = 1;//初始化第一行，只有当前硬币的整数倍才可能取到

            for (int i = 1; i < len ; i++) {
                for (int j = coins[i]; j <=amount ; j++) {
                    dp[j]+=dp[j-coins[i]];//从前往后
                }
            }
            return dp[amount];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

































